{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Champion I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findChampion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到冠军 I"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一场比赛中共有 <code>n</code> 支队伍，按从 <code>0</code> 到&nbsp; <code>n - 1</code> 编号。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、大小为 <code>n * n</code> 的二维布尔矩阵 <code>grid</code> 。对于满足&nbsp;<code>0 &lt;= i, j &lt;= n - 1</code> 且 <code>i != j</code> 的所有 <code>i, j</code> ：如果 <code>grid[i][j] == 1</code>，那么 <code>i</code> 队比 <code>j</code> 队 <strong>强</strong> ；否则，<code>j</code> 队比 <code>i</code> 队 <strong>强</strong> 。</p>\n",
    "\n",
    "<p>在这场比赛中，如果不存在某支强于 <code>a</code> 队的队伍，则认为 <code>a</code> 队将会是 <strong>冠军</strong> 。</p>\n",
    "\n",
    "<p>返回这场比赛中将会成为冠军的队伍。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,1],[0,0]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>比赛中有两支队伍。\n",
    "grid[0][1] == 1 表示 0 队比 1 队强。所以 0 队是冠军。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,0,1],[1,0,1],[0,0,0]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>比赛中有三支队伍。\n",
    "grid[1][0] == 1 表示 1 队比 0 队强。\n",
    "grid[1][2] == 1 表示 1 队比 2 队强。\n",
    "所以 1 队是冠军。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>grid[i][j]</code> 的值为 <code>0</code> 或 <code>1</code><meta charset=\"UTF-8\" /></li>\n",
    "\t<li>对于所有&nbsp;<code>i</code>，<code> grid[i][i]</code>&nbsp;等于&nbsp;<code>0.</code></li>\n",
    "\t<li>对于满足&nbsp;<code>i != j</code> 的所有 <code>i, j</code> ，<code>grid[i][j] != grid[j][i]</code> 均成立</li>\n",
    "\t<li>生成的输入满足：如果 <code>a</code> 队比 <code>b</code> 队强，<code>b</code> 队比 <code>c</code> 队强，那么 <code>a</code> 队比 <code>c</code> 队强</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-champion-i](https://leetcode.cn/problems/find-champion-i/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-champion-i](https://leetcode.cn/problems/find-champion-i/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[0,0]]', '[[0,0,1],[1,0,1],[0,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findChampion(self, grid: List[List[int]]) -> int:\n",
    "        N = len(grid)\n",
    "        for i in range(N):\n",
    "            flag = 1\n",
    "            for j in range(N):\n",
    "                if grid[i][j] == 1 or i == j:\n",
    "                    continue\n",
    "                else:\n",
    "                    flag = 0\n",
    "                    break\n",
    "            if flag == 1:\n",
    "                \n",
    "                return i\n",
    "                        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findChampion(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        for j in range(n):\n",
    "            if sum([grid[i][j] for i in range(n)])==0:\n",
    "                 return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findChampion(self, grid: List[List[int]]) -> int:\n",
    "        max_=0\n",
    "        t=0\n",
    "        for i,x in enumerate(grid):\n",
    "            if sum(x)>max_:\n",
    "                max_=sum(x)\n",
    "                t=i\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findChampion(self, grid: List[List[int]]) -> int:\n",
    "        for j, col in enumerate(zip(*grid)):\n",
    "            if 1 not in col:  # 没有队伍可以击败 j\n",
    "                return j\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
